import collections


class Solution(object):
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        envelopes = [tuple(en) for en in envelopes]
        envelopes = list(set(envelopes))
        envelopes.sort()
        stack = collections.deque()
        stack.append({envelopes[0]})

        def search_split(en, left, right):
            if left == right:
                remove_item = None
                for item in stack[left]:
                    if en[0] < item[0] and en[1] < item[1]:
                        remove_item = item
                        break
                if remove_item:
                    stack[left].remove(remove_item)
                stack[left].add(en)
            else:
                mid = (left + right) // 2
                flag = False
                for item in stack[mid]:
                    if en[0] > item[0] and en[1] > item[1]:
                        flag = True
                        break
                if flag:
                    search_split(en, mid + 1, right)
                else:
                    search_split(en, left, mid)

        for en in envelopes:
            flag = False
            for item in stack[-1]:
                if en[0] > item[0] and en[1] > item[1]:
                    stack.append({en})
                    flag = True
                    break
            if not flag:
                search_split(en, 0, len(stack) - 1)

        return len(stack)


data = Solution()
envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]]
print(data.maxEnvelopes(envelopes))
